package main.leetcode.clockin.May;

import java.util.HashMap;
import java.util.Map;

/**
 * 560.和为K的子数组
 *
 * <p>给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
 *
 * <p>示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
 *
 * <p>说明 : 数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day15 {
    public static void main(String[] args) {
        System.out.println(new day15().subarraySum(new int[] {1, 1, 1}, 2));
        System.out.println(new day15().subarraySum(new int[] {2, 1, 1, 1}, 2));
        System.out.println(new day15().subarraySum(new int[] {1, 2, 3}, 3));
        System.out.println(new day15().subarraySum(new int[] {1}, 3));
        System.out.println(new day15().subarraySum(new int[] {-1, -1, 1}, 3));
    }

    // 滑动窗口，不可行，因为有负数的存在
    //    public int subarraySum(int[] nums, int k) {
    //        int n = nums.length;
    //        if (n < 2) {
    //            return n == 0 ? 0 : (nums[0] == k ? 1 : 0);
    //        }
    //        int res = 0;
    //        int i = 0, j = 1;
    //        int sum = nums[0];
    //        while (j <= n) {
    //            if (sum > k) {
    //                sum -= nums[i++];
    //            } else if (sum < k) {
    //                if (j == n) {
    //                    break;
    //                }
    //                sum += nums[j++];
    //            } else {
    //                ++res;
    //                sum -= nums[i++];
    //            }
    //        }
    //        return res;
    //    }

    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        if (n < 1) {
            return 0;
        }
        Map<Integer, Integer> pre = new HashMap<>();
        pre.put(0, 1);
        int sum = 0, res = 0;
        for (int num : nums) {
            sum += num;
            if (pre.containsKey(sum - k)) {
                res += pre.get(sum - k);
            }
            pre.put(sum, pre.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}
